package org.renwei.alg.heap;

import com.google.common.collect.Lists;

import java.util.List;

/**
 * 二叉堆 （最大堆）
 * 堆的性质： 堆中任意节点的值总是不大于（不小于）其子节点的值；堆总是一棵完全树
 * 数组实现的堆中，第N个节点的左孩子的索引值是（2N+1），右孩子的索引是（2N+2）
 * Created by renwei on 16/8/18.
 */
public class MaxHeap<T extends Comparable> {

    private List<T> mHeap;

    public MaxHeap() {
        this.mHeap = Lists.newArrayList();
    }

    /**
     * 最大堆的向下调整算法（从start开始向下直到end，调整堆）
     *
     * @param start 被下调节点的起始位置（一般为0，表示从第1个开始）
     * @param end   截止范围（一般为数组中的最后一个元素的索引）
     */
    protected void filterdown(int start, int end) {
        int i = start;          //当前节点位置
        int l = 2 * i + 1;      //左孩子的位置
        T tmp = mHeap.get(i);   //当前节点的数值

        while (l <= end) {
            if (l < end && mHeap.get(l).compareTo(mHeap.get(l + 1)) < 0) {
                l++;
            }

            if (tmp.compareTo(mHeap.get(l)) >= 0) {
                break;
            } else {
                mHeap.set(i, mHeap.get(l));
                i = l;
                l = 2 * l + 1;
            }
        }
        mHeap.set(i, tmp);

    }

    /**
     * 最大堆得的向上调整算法（从start开始向上直到end，调整堆）
     * 先将数据加入到最大堆的最后，然后尽可能把这个元素往上挪，直到挪不动为止
     *
     * @param start 被上调节点的起始位置（一般为数组中最后一个元素的索引）
     * @param end   截止范围 （一般为0）
     */
    protected void filterup(int start, int end) {
        int i = start;              //当前节点的位置
        int p = (i - 1) / 2;        //父节点的位置
        T tmp = mHeap.get(i);       //当前节点的数值

        while (i > end) {
            if (mHeap.get(p).compareTo(tmp) >= 0) {
                break;
            } else {
                mHeap.set(i, mHeap.get(p));
                i = p;
                p = (p - 1) / 2;
            }
        }
        mHeap.set(i, tmp);
    }

    /**
     * 删除最大堆中的data
     *
     * @param data
     * @return 0成功 -1失败
     */
    public int remove(T data) {
        if (mHeap.isEmpty()) {
            return -1;
        }

        int index = mHeap.indexOf(data);
        if (-1 == index) {
            return -1;
        }

        int size = mHeap.size();
        mHeap.set(index, mHeap.get(size - 1));  //用最后元素填补
        mHeap.remove(size - 1);   //删除最后的元素

        if (mHeap.size() > 1) {
            filterdown(index, mHeap.size() - 1);  //从index号位置开始自上向下调整为最大堆
        }

        return -1;
    }

    /**
     * 插入data
     *
     * @param data
     */
    public void insert(T data) {
        mHeap.add(data);
        filterup(mHeap.size() - 1, 0);
    }

    @Override public String toString() {
        return "MaxHeap{" +
            "mHeap=" + mHeap +
            '}';
    }

    public static void main(String[] args) {
        int arr[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
        MaxHeap<Integer> tree = new MaxHeap<Integer>();

        for (int i = 0; i < arr.length; i++) {
            tree.insert(arr[i]);
        }
        System.out.println(tree);

        tree.insert(15);
        System.out.println(tree);

        tree.remove(10);
        System.out.println(tree);

    }
}
